Search Results

Documents authored by Kavitha, Telikepalli

Found 2 Possible Name Variants:

Kavitha, Telikepalli

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.43
Perfect Matchings and Popularity in the Many-To-Many Setting

Authors: Telikepalli Kavitha and Kazuhisa Makino

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
We consider a matching problem in a bipartite graph G where every vertex has a capacity and a strict preference list ranking its neighbors. We assume that G admits a perfect matching, i.e., one that fully matches all vertices. It is only perfect matchings that are feasible here and we seek one that is popular within the set of perfect matchings - it is known that such a matching exists in G and can be efficiently computed. Now we are in the weighted setting, i.e., there is a cost function on the edge set, and we seek a min-cost popular perfect matching in G. We show that such a matching can be computed in polynomial time. Our main technical result shows that every popular perfect matching in a hospitals/residents instance G can be realized as a popular perfect matching in the marriage instance obtained by cloning vertices. Interestingly, it is known that such a mapping does not hold for popular matchings in a hospitals/residents instance.
Cite as

Telikepalli Kavitha and Kazuhisa Makino. Perfect Matchings and Popularity in the Many-To-Many Setting. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kavitha_et_al:LIPIcs.FSTTCS.2023.43,
  author =	{Kavitha, Telikepalli and Makino, Kazuhisa},
  title =	{{Perfect Matchings and Popularity in the Many-To-Many Setting}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.43},
  URN =		{urn:nbn:de:0030-drops-194167},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.43},
  annote =	{Keywords: Bipartite graphs, Matchings under preferences, Capacities, Dual certificates}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.22
Stable Matchings with One-Sided Ties and Approximate Popularity

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices in A rank their neighbors in a strict order of preference while vertices in B are allowed to have weak rankings, i.e., ties are allowed in their preferences. Stable matchings always exist in G and are easy to find, however popular matchings need not exist and it is NP-complete to decide if one exists. This motivates the "approximately popular" matching problem. A well-known measure of approximate popularity is low unpopularity factor. We show that when each tie in G has length at most k, there always exists a stable matching whose unpopularity factor is at most k. Our proof is algorithmic and we compute such a stable matching in polynomial time. Our result can be considered to be a generalization of Gärdenfors' result (1975) which showed that when rankings are strict, every stable matching is popular. There are several applications where the size of the matching is its most important attribute. What one seeks here is a maximum matching M such that there is no maximum matching more popular than M. When rankings are weak, it is NP-hard to decide if G admits such a matching. When ties are one-sided and of length at most k, we show a polynomial time algorithm to find a maximum matching whose unpopularity factor within the set of maximum matchings is at most 2k.
Cite as

Telikepalli Kavitha. Stable Matchings with One-Sided Ties and Approximate Popularity. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2022.22,
  author =	{Kavitha, Telikepalli},
  title =	{{Stable Matchings with One-Sided Ties and Approximate Popularity}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.22},
  URN =		{urn:nbn:de:0030-drops-174144},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.22},
  annote =	{Keywords: Bipartite graphs, Maximum matchings, Unpopularity factor}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.41
Fairly Popular Matchings and Optimality

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We consider a matching problem in a bipartite graph G = (A ∪ B, E) where vertices have strict preferences over their neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M is at least the number that prefer N; thus M does not lose a head-to-head election against any matching where vertices are voters. It is easy to find popular matchings; however when there are edge costs, it is NP-hard to find (or even approximate) a min-cost popular matching. This hardness motivates relaxations of popularity. Here we introduce fairly popular matchings. A fairly popular matching may lose elections but there is no good matching (wrt popularity) that defeats a fairly popular matching. In particular, any matching that defeats a fairly popular matching does not occur in the support of any popular mixed matching. We show that a min-cost fairly popular matching can be computed in polynomial time and the fairly popular matching polytope has a compact extended formulation. We also show the following hardness result: given a matching M, it is NP-complete to decide if there exists a popular matching that defeats M. Interestingly, there exists a set K of at most m popular matchings in G (where |E| = m) such that if a matching is defeated by some popular matching in G then it has to be defeated by one of the matchings in K.
Cite as

Telikepalli Kavitha. Fairly Popular Matchings and Optimality. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.STACS.2022.41,
  author =	{Kavitha, Telikepalli},
  title =	{{Fairly Popular Matchings and Optimality}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.41},
  URN =		{urn:nbn:de:0030-drops-158516},
  doi =		{10.4230/LIPIcs.STACS.2022.41},
  annote =	{Keywords: Bipartite graphs, Stable matchings, Mixed matchings, Polytopes}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.25
Matchings, Critical Nodes, and Popular Solutions

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
We consider a matching problem in a marriage instance G. Every node has a strict preference order ranking its neighbors. There is a set C of prioritized or critical nodes and we are interested in only those matchings that match as many critical nodes as possible. Such matchings are useful in several applications and we call them critical matchings. A stable matching need not be critical. We consider a well-studied relaxation of stability called popularity. Our goal is to find a popular critical matching, i.e., a weak Condorcet winner within the set of critical matchings where nodes are voters. We show that popular critical matchings always exist in G and min-size/max-size such matchings can be efficiently computed.
Cite as

Telikepalli Kavitha. Matchings, Critical Nodes, and Popular Solutions. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2021.25,
  author =	{Kavitha, Telikepalli},
  title =	{{Matchings, Critical Nodes, and Popular Solutions}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.25},
  URN =		{urn:nbn:de:0030-drops-155360},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.25},
  annote =	{Keywords: Bipartite graphs, Stable matchings, LP-duality}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.85
Maximum Matchings and Popularity

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Let G be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching M in G is a popular max-matching if for any maximum matching N in G, the number of nodes that prefer M is at least the number that prefer N. Popular max-matchings always exist in G and they are relevant in applications where the size of the matching is of higher priority than node preferences. Here we assume there is also a cost function on the edge set. So what we seek is a min-cost popular max-matching. Our main result is that such a matching can be computed in polynomial time. We show a compact extended formulation for the popular max-matching polytope and the algorithmic result follows from this. In contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard.
Cite as

Telikepalli Kavitha. Maximum Matchings and Popularity. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 85:1-85:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.ICALP.2021.85,
  author =	{Kavitha, Telikepalli},
  title =	{{Maximum Matchings and Popularity}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{85:1--85:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.85},
  URN =		{urn:nbn:de:0030-drops-141548},
  doi =		{10.4230/LIPIcs.ICALP.2021.85},
  annote =	{Keywords: Bipartite graphs, Popular matchings, Stable matchings, Dual certificates}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.25
Min-Cost Popular Matchings

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
Let G = (A ∪ B, E) be a bipartite graph on n vertices where every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if there is no matching N such that vertices that prefer N to M outnumber those that prefer M to N. Popular matchings always exist in G since every stable matching is popular. Thus it is easy to find a popular matching in G - however it is NP-hard to compute a min-cost popular matching in G when there is a cost function on the edge set; moreover it is NP-hard to approximate this to any multiplicative factor. An O^*(2ⁿ) algorithm to compute a min-cost popular matching in G follows from known results. Here we show: - an algorithm with running time O^*(2^{n/4}) ≈ O^*(1.19ⁿ) to compute a min-cost popular matching; - assume all edge costs are non-negative - then given ε > 0, a randomized algorithm with running time poly(n,1/(ε)) to compute a matching M such that cost(M) is at most twice the optimal cost and with high probability, the fraction of all matchings more popular than M is at most 1/2+ε.
Cite as

Telikepalli Kavitha. Min-Cost Popular Matchings. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2020.25,
  author =	{Kavitha, Telikepalli},
  title =	{{Min-Cost Popular Matchings}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.25},
  URN =		{urn:nbn:de:0030-drops-132668},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.25},
  annote =	{Keywords: Bipartite graphs, Stable matchings, Dual certificates}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.70
Popular Matchings with One-Sided Bias

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Let G = (A ∪ B,E) be a bipartite graph where A consists of agents or main players and B consists of jobs or secondary players. Every vertex has a strict ranking of its neighbors. A matching M is popular if for any matching N, the number of vertices that prefer M to N is at least the number that prefer N to M. Popular matchings always exist in G since every stable matching is popular. A matching M is A-popular if for any matching N, the number of agents (i.e., vertices in A) that prefer M to N is at least the number of agents that prefer N to M. Unlike popular matchings, A-popular matchings need not exist in a given instance G and there is a simple linear time algorithm to decide if G admits an A-popular matching and compute one, if so. We consider the problem of deciding if G admits a matching that is both popular and A-popular and finding one, if so. We call such matchings fully popular. A fully popular matching is useful when A is the more important side - so along with overall popularity, we would like to maintain "popularity within the set A". A fully popular matching is not necessarily a min-size/max-size popular matching and all known polynomial time algorithms for popular matching problems compute either min-size or max-size popular matchings. Here we show a linear time algorithm for the fully popular matching problem, thus our result shows a new tractable subclass of popular matchings.
Cite as

Telikepalli Kavitha. Popular Matchings with One-Sided Bias. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.ICALP.2020.70,
  author =	{Kavitha, Telikepalli},
  title =	{{Popular Matchings with One-Sided Bias}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{70:1--70:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.70},
  URN =		{urn:nbn:de:0030-drops-124774},
  doi =		{10.4230/LIPIcs.ICALP.2020.70},
  annote =	{Keywords: Bipartite graphs, Stable matchings, Gale-Shapley algorithm, LP-duality}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.20
Popular Roommates in Simply Exponential Time

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
We consider the popular matching problem in a graph G = (V,E) on n vertices with strict preferences. A matching M is popular if there is no matching N in G such that vertices that prefer N to M outnumber those that prefer M to N. It is known that it is NP-hard to decide if G has a popular matching or not. There is no faster algorithm known for this problem than the brute force algorithm that could take n! time. Here we show a simply exponential time algorithm for this problem, i.e., one that runs in O^*(k^n) time, where k is a constant. We use the recent breakthrough result on the maximum number of stable matchings possible in such instances to analyze our algorithm for the popular matching problem. We identify a natural (also, hard) subclass of popular matchings called truly popular matchings and show an O^*(2^n) time algorithm for the truly popular matching problem.
Cite as

Telikepalli Kavitha. Popular Roommates in Simply Exponential Time. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2019.20,
  author =	{Kavitha, Telikepalli},
  title =	{{Popular Roommates in Simply Exponential Time}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.20},
  URN =		{urn:nbn:de:0030-drops-115820},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.20},
  annote =	{Keywords: Roommates instance, Popular matching, Stable matching, Dual certificate}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2019.4
Popular Matchings: Good, Bad, and Mixed (Invited Talk)

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We consider the landscape of popular matchings in a bipartite graph G where every vertex has strict preferences over its neighbors. This is a very well-studied model in two-sided matching markets. A matching M is popular if it does not lose a head-to-head election against any matching, where each vertex casts a vote for the matching where it gets a better assignment. Roughly speaking, a popular matching is one such that there is no matching where more vertices are happier. The notion of popularity is more relaxed than stability: a classical notion studied for the last several decades. Popular matchings always exist in G since stable matchings always exist in a bipartite graph and every stable matching is popular. Algorithmically speaking, the landscape of popular matching seems to have only a few bright spots. Every stable matching is a min-size popular matching and there are also simple linear time algorithms for computing a max-size popular matching and for the popular edge problem. All these algorithms reduce the popular matching problem to an appropriate question in stable matchings and solve the corresponding stable matching problem. We now know NP-hardness results for many popular matching problems. These include the min-cost/max-weight popular matching problem and the problem of deciding if G admits a popular matching that is neither a min-size nor a max-size popular matching. For non-bipartite graphs, it is NP-hard to even decide if a popular matching exists or not. A mixed matching is a probability distribution or a lottery over matchings. A popular mixed matching is one that never loses a head-to-head election against any mixed matching. As an allocation mechanism, a popular mixed matching has several nice properties. Moreover, finding a max-weight or min-cost popular mixed matching in G is easy (by solving a linear program). Interestingly, there is always an optimal popular mixed matching Pi with a simple structure: Pi = {(M_0,1/2),(M_1,1/2)} where M_0 and M_1 are matchings in G. Popular mixed matchings always exist in non-bipartite graphs as well and can be computed in polynomial time.
Cite as

Telikepalli Kavitha. Popular Matchings: Good, Bad, and Mixed (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.MFCS.2019.4,
  author =	{Kavitha, Telikepalli},
  title =	{{Popular Matchings: Good, Bad, and Mixed}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.4},
  URN =		{urn:nbn:de:0030-drops-109489},
  doi =		{10.4230/LIPIcs.MFCS.2019.4},
  annote =	{Keywords: Matchings under preferences, Algorithms, NP-Hardness}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.17
Popular Matchings in Complete Graphs

Authors: Ágnes Cseh and Telikepalli Kavitha

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Our input is a complete graph G = (V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is "globally stable" or popular. A matching M is popular if M does not lose a head-to-head election against any matching M': here each vertex casts a vote for the matching in {M,M'} where it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here.
Cite as

Ágnes Cseh and Telikepalli Kavitha. Popular Matchings in Complete Graphs. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cseh_et_al:LIPIcs.FSTTCS.2018.17,
  author =	{Cseh, \'{A}gnes and Kavitha, Telikepalli},
  title =	{{Popular Matchings in Complete Graphs}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.17},
  URN =		{urn:nbn:de:0030-drops-99164},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.17},
  annote =	{Keywords: popular matching, complete graph, complexity, linear programming}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.19
Popular Matchings with Multiple Partners

Authors: Florian Brandl and Telikepalli Kavitha

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Our input is a bipartite graph G=(A\cup B,E) where each vertex in A\cup B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to cap(a)\geq 1 many courses while each course b seeks cap(b)\geq 1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G - a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.
Cite as

Florian Brandl and Telikepalli Kavitha. Popular Matchings with Multiple Partners. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brandl_et_al:LIPIcs.FSTTCS.2017.19,
  author =	{Brandl, Florian and Kavitha, Telikepalli},
  title =	{{Popular Matchings with Multiple Partners}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.19},
  URN =		{urn:nbn:de:0030-drops-83765},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.19},
  annote =	{Keywords: Bipartite graphs, Linear programming duality, Gale-Shapley algorithm}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.22
Popular Half-Integral Matchings

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
In an instance G = (A union B, E) of the stable marriage problem with strict and possibly incomplete preference lists, a matching M is popular if there is no matching M0 where the vertices that prefer M' to M outnumber those that prefer M to M'. All stable matchings are popular and there is a simple linear time algorithm to compute a maximum-size popular matching. More generally, what we seek is a min-cost popular matching where we assume there is a cost function c : E -> Q. However there is no polynomial time algorithm currently known for solving this problem. Here we consider the following generalization of a popular matching called a popular half-integral matching: this is a fractional matching ~x = (M_1 + M_2)/2, where M1 and M2 are the 0-1 edge incidence vectors of matchings in G, such that ~x satisfies popularity constraints. We show that every popular half-integral matching is equivalent to a stable matching in a larger graph G^*. This allows us to solve the min-cost popular half-integral matching problem in polynomial time.
Cite as

Telikepalli Kavitha. Popular Half-Integral Matchings. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.ICALP.2016.22,
  author =	{Kavitha, Telikepalli},
  title =	{{Popular Half-Integral Matchings}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.22},
  URN =		{urn:nbn:de:0030-drops-63011},
  doi =		{10.4230/LIPIcs.ICALP.2016.22},
  annote =	{Keywords: bipartite graphs, stable matchings, fractional matchings, polytopes}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.513
New Pairwise Spanners

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
Let G = (V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch \beta if for every (u,v) \in V \times V, \mathsf{dist}_H(u,v) \le \mathsf{dist}_G(u,v) + \beta. The problem of computing sparse spanners with small stretch \beta is well-studied. Here we consider the following relaxation: we are given \p\subseteq V \times V and we seek a sparse subgraph H where \mathsf{dist}_H(u,v)\le \mathsf{dist}_G(u,v) + \beta for each (u,v) \in \p. Such a subgraph is called a pairwise spanner with additive stretch \beta and our goal is to construct such subgraphs that are sparser than all-pairs spanners with the same stretch. We show sparse pairwise spanners with additive stretch 4 and with additive stretch 6. We also consider the following special cases: \p = S \times V and \p = S \times T, where S\subseteq V and T\subseteq V, and show sparser pairwise spanners for these cases.
Cite as

Telikepalli Kavitha. New Pairwise Spanners. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 513-526, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.STACS.2015.513,
  author =	{Kavitha, Telikepalli},
  title =	{{New Pairwise Spanners}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{513--526},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.513},
  URN =		{urn:nbn:de:0030-drops-49381},
  doi =		{10.4230/LIPIcs.STACS.2015.513},
  annote =	{Keywords: undirected graphs, spanners, approximate distances, additive stretch}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.339
Fair Matchings and Related Problems

Authors: Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
Let G = (A union B, E) be a bipartite graph, where every vertex ranks its neighbors in an order of preference (with ties allowed) and let r be the worst rank used. A matching M is fair in G if it has maximum cardinality, subject to this, M matches the minimum number of vertices to rank r neighbors, subject to that, M matches the minimum number of vertices to rank (r-1) neighbors, and so on. We show an efficient combinatorial algorithm based on LP duality to compute a fair matching in G. We also show a scaling based algorithm for the fair b-matching problem. Our two algorithms can be extended to solve other profile-based matching problems. In designing our combinatorial algorithm, we show how to solve a generalized version of the minimum weighted vertex cover problem in bipartite graphs, using a single-source shortest paths computation---this can be of independent interest.
Cite as

Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail. Fair Matchings and Related Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 339-350, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.FSTTCS.2013.339,
  author =	{Huang, Chien-Chung and Kavitha, Telikepalli and Mehlhorn, Kurt and Michail, Dimitrios},
  title =	{{Fair Matchings and Related Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{339--350},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.339},
  URN =		{urn:nbn:de:0030-drops-43841},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.339},
  annote =	{Keywords: Matching with Preferences, Fairness and Rank-Maximality, Bipartite Vertex Cover, Linear Programming Duality, Complementary Slackness}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2012
LIPIcs, Volume 18, FSTTCS'12, Complete Volume

Authors: Deepak D'Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
LIPIcs, Volume 18, FSTTCS'12, Complete Volume
Cite as

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{dsouza_et_al:LIPIcs.FSTTCS.2012,
  title =	{{LIPIcs, Volume 18, FSTTCS'12, Complete Volume}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012},
  URN =		{urn:nbn:de:0030-drops-41121},
  doi =		{10.4230/LIPIcs.FSTTCS.2012},
  annote =	{Keywords: Software/Program Verification, Models of Computation, Modes of Computation, Complexity Measures and Classes, Nonnumerical Algorithms and Problems Specifying and Verifying and Reasoning about Programs, Mathematical Logic, Formal Languages}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.209
On Pairwise Spanners

Authors: Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Given an undirected n-node unweighted graph G = (V, E), a spanner with stretch function f(.) is a subgraph H \subseteq G such that, if two nodes are at distance d in G, then they are at distance at most f(d) in H. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the u-v distance only for pairs (u,v) in a given set P \subseteq V x V. Such P-spanners were studied before [Coppersmith,Elkin'05] only in the special case that f(.) is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same P) and of the best known spanners (with the same f(.)). In more detail, for arbitrary P, we show that there exists a P-spanner of size O(n(|P|log n)^{1/4}) with f(d) = d + 4 log n. Alternatively, for any epsislon > 0, there exists a P-spanner of size O(n|P|^{1/4} sqrt{(log n) / epsilon}) with f(d) = (1 + epsilon)d + 4. We also consider the relevant special case that there is a critical set of nodes S \subseteq V, and we wish to approximate either the distances within nodes in S or from nodes in S to any other node. We show that there exists an (S x S)-spanner of size O(n sqrt{|S|}) with f(d) = d + 2, and an (S x V)-spanner of size O(n sqrt{|S| log n}) with f(d) = d + 2 log n. All the mentioned pairwise spanners can be constructed in polynomial time.
Cite as

Marek Cygan, Fabrizio Grandoni, and Telikepalli Kavitha. On Pairwise Spanners. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 209-220, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{cygan_et_al:LIPIcs.STACS.2013.209,
  author =	{Cygan, Marek and Grandoni, Fabrizio and Kavitha, Telikepalli},
  title =	{{On Pairwise Spanners}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{209--220},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.209},
  URN =		{urn:nbn:de:0030-drops-39353},
  doi =		{10.4230/LIPIcs.STACS.2013.209},
  annote =	{Keywords: Undirected graphs, shortest paths, additive spanners, distance preservers}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1759
Dynamic matrix rank with partial lookahead

Authors: Telikepalli Kavitha

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We consider the problem of maintaining information about the rank of a matrix $M$ under changes to its entries. For an $n \times n$ matrix $M$, we show an amortized upper bound of $O(n^{\omega-1})$ arithmetic operations per change for this problem, where $\omega < 2.376$ is the exponent for matrix multiplication, under the assumption that there is a {\em lookahead} of up to $\Theta(n)$ locations. That is, we know up to the next $\Theta(n)$ locations $(i_1,j_1),(i_2,j_2),\ldots,$ whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner.
Cite as

Telikepalli Kavitha. Dynamic matrix rank with partial lookahead. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 268-279, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kavitha:LIPIcs.FSTTCS.2008.1759,
  author =	{Kavitha, Telikepalli},
  title =	{{Dynamic matrix rank with partial lookahead}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{268--279},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1759},
  URN =		{urn:nbn:de:0030-drops-17594},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1759},
  annote =	{Keywords: Matrix rank, dynamic algorithm, fast matrix multiplication}
}

Telikepalli, Kavitha

Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2012.i
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Deepak D'Souza, Jaikumar Radhakrishnan, and Kavitha Telikepalli

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
Frontmatter, Table of Contents, Preface, Conference Organization
Cite as

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{dsouza_et_al:LIPIcs.FSTTCS.2012.i,
  author =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.i},
  URN =		{urn:nbn:de:0030-drops-38411},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact